package com.jacklei;

import com.jacklei.util.ArrUtil;

import java.util.Arrays;

//归并排序
public class MergeSort {
    public static void main(String[] args) {
        int[] arr = ArrUtil.getRandomArr();
        int[] arr1 = ArrUtil.copyArr(arr);

        Arrays.sort(arr);
        sort(arr1);
        ArrUtil.checkArr(arr,arr1);
        ArrUtil.seeArr(arr,arr1);

    }

    public static void sort(int[] arr ,int l, int r){
        if (l>=r)return;
        int medianIndex = l + ((r-l)>>1);
        sort(arr, l, medianIndex);
        sort(arr,medianIndex+1, r);
        merge(arr, l, medianIndex, r);

    }
    public static void sort(int[] arr){
        sort(arr,0,arr.length-1);
    }

    private static void merge(int[] arr, int l, int medianIndex, int r) {
        int[] result = new int[r-l+1];
        int index = 0;
        int i = l;
        int j =medianIndex+1;

        while(i<= medianIndex && r >= j){
            result[index++] = arr[i] > arr[j] ? arr[j++] : arr[i++];
        }
        while(i<= medianIndex)
            result[index++] = arr[i++];
        while(r >= j)
            result[index++] = arr[j++];

        for (int k = l , o=0; k <= r;) {
            arr[k++] =  result[o++];
        }
    }
}
